In the context of memory management, garbage collection is an important task which identifies and collects memory objects that were previously allocated for a given computer application, and are no longer used thereby. Consider, for example, a continuous (and relatively large) heap (10) (see FIG. 1) and a smaller, so called "root memory module" (12), representative of memory currently in use by one or more computer applications.
All those objects (14) that are directly or indirectly reachable from the root by pointers are "alive" and should not be collected. In contrast thereto, all the objects (16) which have no reference pointers are effectively no longer in use and are therefore regarded as garbage that should be collected. After collection, only active objects are maintained in the heap and memory space that has just been released due to garbage collection, may be allocated for new applications.
The standard approach of scanning the entire heap in order to identify and collect garbage objects is time consuming and therefore an improved scheme called `generational collection` [5] has been developed, and is now a well accepted solution for reducing price times induced by garbage collection. Generational garbage collectors rely on the assumption that many objects die young. Under this assumption, it is useful to collect the garbage in the young area more frequently. Young objects that survive several collections are "promoted" to the older generation. Since the young generation is kept small, most collections are fast and do not stall the application for too long.
An improved solution for reducing delay tine imposed by the garbage collection procedure, for "young" generations is disclosed in a co-pending U.S. patent application Ser. No. 09/139,752 assigned to the present Applicant and filed simultaneously to the present application, and entitled "A Method for Combining Card Marking With a Remembered bet for Generational Garbage Collection With More Then Two Generations". The contents of U.S. patent application Ser. No. 09/139,752 are incorporated herein by reference.
Considering that "older" generations occupy, as a rule, larger part of the heap (as compared to the younger one) the garbage collection procedure is by default longer, and conventional garbage collection application that are applicable to the relatively small young generation area are as a rule inefficient, in terms of processing overhead, for the relatively large old area of the heap.
In the context of the present invention, reference is made to a so-called "train" algorithm which is known per se (see discussion below) and to two data structures, i.e. remembered sets and card markings. Whilst in the present invention card marking and remembered sets data structures are utilized by the train algorithm (for "old" generation GC), there follows a brief description of the specified data structures in connection with a more simple application, i.e. tracking inter-generational pointers in a young generation GC.
Thus, FIG. 2 illustrates schematically a generational garbage collection scheme, wherein the heap (20) is partitioned into two areas: young and old, (21) and (22), respectively. The young area (21) is scanned more frequently and after garbage objects therein are collected and some of the surviving objects are moved to the old area, objects may be allocated in the young area for new applications. The advantages of the generational garbage collection approach are:
1. Most collections are fast and efficient: they concentrate on the young area where it is expected to find a high percentage of garbage. PA1 2. The heap is frequently collected. Thus the heap is frequently reused. PA1 3. The collector uses a smaller working set since most collections only scan a small part of the heap. PA1 4. The specified advantages (2 and 3) give rise to overall better system behavior with less paging: i.e. the collector traces through fewer pages and the program maintains a small working set since the heap is reused. PA1 (a) partitioning said heap or portion thereof into at least one old and at least one young area; PA1 (b) associating said at least one old area with cars that form part of said at least one old area, card markings and remembered sets data structure; said card markings including, for each card, a card time stamp indicative of a time said card was updated; each of said cars including, a respective car time stamp indicative of a time the remembered set of said car was updated; PA1 (c) identifying all cards that were updated later than the remembered set of a selected one of said cars and in respect of each card thus identified: PA1 (d) updating the car time stamp associated with said selected car; PA1 processor communicating with said memory, and being capable of: PA1 memory heap or portion thereof that is partitioned into at least one old and at least one young areas; said at least one old area is associate at least cars that form part of said at least one old area, card markings and remembered sets data structure; said card markings includes, for each card, a card time stamp indicative of the time said card was updated; said car includes, for each car, a car time stamp indicative of the time the remembered set of said car was updated. PA1 an action is taken according to a decision criterion that includes the stipulation that the first counter value is larger or equal to the second counter value; PA1 a method is capable of handling a counter overflow event whereby the counter is incremented beyond said range, the method further includes the steps of: PA1 an action is taken according to a decision criterion that includes the stipulation that the first counter value is larger or equal to the second counter value; PA1 the processor is capable of handling a counter overflow event whereby the counter is incremented beyond said range; said processor includes:
Since, only part of the heap is scanned, it is required to identify not only those pointers that reference objects from the root to the young area (e.g. pointer (25), but also inter-generational pointers (e.g. (26), i.e. pointers that originate from objects residing in the old generation and reference objects in the young generation. As will be explained in greater detail below, data structures are known in the literature which assist in rapidly identifying the inter-generational pointers for GC purposes.
In a generational scheme, typically, when a generation is subject to GC, all the younger generations are also collected. This reduces the bookkeeping for inter-generational pointers, so that only pointers from older to younger generations need to be maintained. Typically, the number of such pointers is relatively small and, thus, generational collections can use a data structure to maintain an (almost) updated list of these inter-generational pointers. Two possible data structures are suggested in the prior art [5], [7] and [8]: card marking and remembered sets. A combination of the two is suggested in [3].
One way to record inter-generational pointers for a given generation is to maintain a remembered set for the generation [5] and [8]. In the remembered set of generation g, all locations of the inter-generational pointers that reference objects in generation g are kept. Maintenance of this set is done by the application whenever a pointer is modified, and by the collector when objects are promoted. Variations on this method are discussed in [1] and [9].
Maintaining the remembered set imposes a costly overhead on the application during normal operation seeing that any change of a pointer necessitates insertion and/or deletion of a member in the remembered set. Card marking reduces this cost [7]. Here, the heap is partitioned into cards of equal size, and whenever the application modifies an object in a card, it marks the card as dirty. Marking a card is a very short operation for the user program [2], [7], [10]. Depending on the specific processor, it may be implemented in 3 to 6 instructions. However, the collector performs more work in a card marking system. It must scan all the dirty cards to find the inter-generational pointers, instead of just getting the pointer from the remembered set. Dirty cards are cards that were recently modified by the application some of which contain inter-generational pointers, the latter being scanned repeatedly.
The advantage of combining these two methods is pointed out by Hosking and Moss [3]. After scanning a card once to find all modifications, the relevant inter-generational pointers can be kept in a remembered set and the card need not be scanned again unless it is modified. This keeps the advantage of low overhead on the application, but also increases the collector efficiency, since cards are scanned once and rot repeatedly; their dirty flag is cleared; and only dirty (modified) cards are scanned.
The utilization of conventional remembered sets and card marking data structures poses a significant overhead in a generational scheme. Thus, suppose that a few young generations are collected, all dirty cards are scanned, and the remembered set of each collected generation is updated. The dilemma is whether all the remembered sets, including remembered sets of generations that were not collected should be updated. If in the affirmative, longer delays are caused, while collecting the younger generations. (Recall that updating the remembered sets means removing all entrees that have become relevant plus adding entries for new inter-generational pointers). On the other hand, if not all the remembered sets are updated, then the mark of the card cannot be cleared, since it has not been scanned for older generations. The inevitable consequence of failing to clear the marks is that the card is unnecessarily scanned again and again during future collections of the young generations.
Having described, in general, the remembered sets and card markings data structures (although in connection with young generation GC), there follows now a brief description of the so called train algorithm for old generation GC.
Hudson and Moss [4] suggest use of the train algorithm to cope with the problem of scanning the relatively large old area of the heap which, if otherwise implemented in a standard (long) sequential scanning of the heap, could lead to undue stalls and delays of the user program. The train algorithm partitions the old generation into parts called cars, and collects one car at time.
The problem with a naive implementation of this idea is that cycles of garbage that spread among several cars cannot be collected. Thus, the cars are grouped into trains, and the algorithm aims at relocating clusters of garbage into a single train and at the same time, relocating living objects (that are not part of the cluster) out of the train. Motivations, details and an implementation of the train algorithm are to be found in the prior art [4] and [6]. Only those details of the algorithm that are relevant for the present application are now discussed.
First, when a car is collected, the young generation is collected as well. Actually, the young generation may sometimes be collected without any car collection. Second, trains are numbered, cars and numbered, and the lowest car in the lowest train is chosen for collection. During this collection, objects are moved out of the car into other trains or the same train. Sometimes the objects are moved into existing cars and sometimes new cars are created to store them. These new cars may reside in an existing train or a new train may be created for them. After all live objects are moved from the car being collected, the car is reclaimed for future allocations. The remaining objects that are promoted from the young generation may also go into either old or new cars in various trains.
Each car has a remembered set so that when a car is collected, incoming pointers may be located efficiently. This remembered set is used to keep track of pointers that go from other cars into this car. It is not necessary to keep track of pointers that reference this car from the young generation, since the young generation is fully scanned during each collection, and thus all pointers from the young generation into the collected car will be discovered during this scan.
In order to keep the overhead during normal operation low, it has been proposed to combine card marking with the remembered set method as suggested in [3], [4]. The old heap is partitioned into cards and when the application modifies a card, it marks the card "dirty". When a car has to be scanned, all dirty cards are scanned and the remembered set is updated and later used to find roots for the collection.
Similar to the young GC application described above, the same dilemma of updating the remembered sets arises. Thus, there are only few remembered sets that are relevant to the current collection, and it is desired to avoid updating all the remembered sets considering that there are, as a rule, many of them (as many as the number of cars that are spread over the old generation). It is therefore desired to keep track of which cards should be scanned for which car collection. Otherwise, the cards are rescanned again and again.
There is accordingly a need in the art to substantially reduce or overcome the inherent limitations of hitherto implementations of the train algorithm that utilize remembered sets and card markings data structures for old generation GC applications.